Enlaces punto a punto (página 2)

Partes: 1, 2

Algoritmo de Checksum en Internet
Mensaje una secuencia 16-bit integers; sum usando 16-bit aritmética complemento a uno; tomar el Ca1 del resultado.

u_short
cksum(u_short *buf, int count)
{
register u_long sum = 0;
while (count–)
{
sum += *buf++;
if (sum & 0xFFFF0000)
{
/* carry occurred, so wrap around */
sum &= 0xFFFF;
sum++;
}
}
return ~(sum & 0xFFFF);
}

Comprobación de sumas: comprobación de redundancia cíclica
Ver datos de bits, D, como número binario.
Escoge un patrón de r+1 bit (generador), G.
Objetivo: escoger r CRC bits, R, como este.
< D,R> división exacta entre G (módulo 2).
El receptor conoce G, divide < D,R> entre G. si el resto no es cero: error detectado.
Puede detectar todos los errores repentinos de menos de r+1 bits.
Muy usado .
D: bits de datos que se envían
Patrónde bits
bits d
bits r
R: bits de CRC

CRC : Cyclic Redundancy Check
Agrego k bits de redundancia a un mensaje de n-bit
Se debe buscar que k < < n
Por ejemplo k = 32 y n = 12,000 (1500 bytes)
Represento mensaje n-bit como un polinomio de grado n-1
MSG=10011010 as M(x) = x7 + x4 + x3 + x1
Sea k el grado de algún polinomio divisor
Ejemplo : C(x) = x3 + x2 + 1

CRC (cont)
TX P(x) que es divisible por C(x)
Desplazo a la izquierda k bits, M(x)xk
Saco el resto de M(x)xk / C(x) de M(x)xk
Polinomio RX P(x) + E(x)
E(x) = 0 implica no error
Divido (P(x) + E(x)) por C(x); queda cero si:
E(x) es cero (no error) o
E(x) es exactamente divisible por C(x)

Ejemplo : C(x) = x4 + x + 1

Protocolos Punto a Punto
Los mensajes llegan en "orden"
Hay errores
Como lograr una comunicación confiable ??
Que hacemos con el CRC ??

Detecto errores , timeout y RTX de tramas ..

Protocolos Punto a Punto (cont)
Mecanismos fundamentales : Reconocimiento (ACK) y Timeouts
Algunos autores esta estrategia general la denominan :

ARQ : Automatic Repeat Request

ACKs (Acknowledgements) y Timeouts

Protocolo Stop-and-Wait ( un bit número de secuencia)
Problema: mantener el "pipe full"
Ejemplo
Enlace de 1.5Mbps x 45ms RTT = 67.5Kb (8KB)
Si 1KB de tamaño de trama, dado que el emisor solo puede enviar una trama por cada RTT
=> 1/8 utilización del enlace (aprox. 182 Kbps)
Sender
Receiver
Trama 0
ACK 0
Trama 1
ACK 1

Protocolo de ventana deslizante (Sliding Window)
Permite múltiples "tramas en vuelo" (outstanding un-ACKed) sin su ACK
Limite superior de tramas sin reconocimiento se denomina ventana (window)

SW: Emisor (TX)
Asigna un numero de secuencia a cada trama (SeqNum)
Mantiene tres variable de estado:
send window size (SWS)
last acknowledgment received (LAR)
last frame sent (LFS)
Mantiene invariante: LFS – LAR < = SWS

Avanza a la derecha LAR cuando ACK llega
Debe mantener buffereados SWS frames
(Gp:) <
(Gp:) SWS
(Gp:) LAR
(Gp:) LFS
(Gp:) ¦ ¦ ¦
(Gp:) ¦ ¦ ¦
(Gp:) –

SW: Receptor (RX)
Mantiene tres variables de estado
receive window size (RWS)
largest frame acceptable (LFA)
last frame received (LFR)
Mantiene invariante: LFA – LFR < = RWS

Cuando llega trama con SeqNum :
if LFR < SeqNum < = LFA => acepto
if SeqNum < = LFR or SeqNum > LFA => descarto
Envío ACKs acumulativos (?? )
(Gp:) RWS
(Gp:) LFR
(Gp:) LAF
(Gp:) ¦ ¦ ¦
(Gp:) ¦ ¦ ¦
(Gp:) <
(Gp:) –

SW: Receptor (cont )
ACKs acumulativos (?? )
Receptor cuando envia un ACK
Sea SeqNumToAck el mayor SeqNum que no recibio ACK
Todos los frames con SeqNum < = SeqNumToAck han sido RX

=> acumulativos
Se setea LFR = SeqNumToAck
LAF =LFR + RWS

Ejemplo
Supongo LFR=5 ( ultimo ACK que envio fue para numero de secuencia 5) y RWS =4
LAF =LFR + RWS => LAF=9
Tramas 7 y 8 están buffereadas
Sin embargo no se envía ACK porque aun no llego trama 6
7 y 8 se dice que llegaron fuera de orden
( técnicamente el RX puede reenviar un ACK 5)

Ejemplo (cont)
Si llega la trama 6 , => ACK 8
LFR=8
LAF =LFR + RWS => LAF=12
Si la trama 6 se pierde , TIMEOUT y RTX

Que efecto produce la perdida de una trama ?? Pipe full ?

Material Complementario
SubProtocolo PPP
Ejemplo de CRC
Eficiencia Ventana Deslizante
Protocolos de ventana deslizante [1]
Técnicas de identificación de tramas [1]
Corrección de Errores

[1]Tanenbaum

Una clasificación de los protocolos de nivel de enlace?
Orientados a Bytes ( BISYNC)
Orientados a Bits ( ??)

Requisitos de diseño de PPP [RFC 1557]
Enmarcado de paquetes: encapsulado de un datagrama de capa de red en un marco de enlace de datos.
Soporta datos de la capa de red de cualquier protocolo de capa de red (no sólo IP) al mismo tiempo.
Capacidad de desmultiplexar hacia arriba.
Transparencia de bits: debe soportar cualquier patrón de bits en el campo de datos.
Detección de errores (sin corrección).
Pervivencia de la conexión: detecta un fallo de señal de enlace en la capa de red.
Negociación de direcciones en la capa de red: punto final puede conocer/configurar las direcciones de la capa de red de los demás.

No se requiere para PPP
Sin corrección o recuperación de errores.
Sin control de flujo.
Estropeado, entrega correcta.
No necesita soportar enlaces multipunto (por ejemplo, elecciones)

La recuperación de errores , el control de flujo,
la reordenación de datos están relegados
a capas superiores.

Enmarcamiento de datos PPP
Flag: delimitador (enmarcamiento).
Dirección: no hace nada (sólo una opción).
Control: no hace nada; en un futuro posible control de campos.
Protocolo: protocolo de capa superior al que se entregan los marcos (por ejemplo, PPP-LCP, IP, IPCP, etc.).
Protocolo
Longitud variable
ó
ó
Información
Comprobación

Enmarcamiento de datos PPP
Información: soporta datos de capas superiores.
Comprobación: comprobación de redundancia cíclica para detectar errores.
Dirección
Protocolo
Longitud variable
ó
ó
Información
Comprobación

Rellenado de bytes
Requisito de "transparencia de datos": el campo de datos tiene que estar autorizado a incluir un patrón de flag < 01111110>
Pregunta: ¿se han recibido < 01111110> datos o flag?

Emisor: "añade" extra < 01111110> byte tras cada < 01111110> byte de datos.
Receptor:
Dos 01111110 bytes en una fila: descarta el primer byte, continúa la recepción de datos.
un 01111110: byte flag

Rellenado de bytes
Patrón de byte flag
en datos para enviar
Patrón de byte flag más byte rellenados en datos transmitidos.

Protocolo de control de datos PPP
Antes de intercambiar datos de la capa de red, los datos de enlace iguales deben:
Configurar enlaces PPP (máxima longitud de marco, autentificación).
Conocer/configurar información de capa de red.
Para IP: soportar el protocolo de control IP (IPCP), mensajes (campo de protocolo: 8021) para configurar/conocer direcciones IP.
Difunto
Terminación
Apertura
Establecimiento
del enlace
Autentificación
Configuración de la
capa de red

Ejemplo CRC
Se pide:
D.2r XOR R = nG
igualmente:
D.2r = nG XOR R
igualmente:
si se divide D.2r entre G, necesitamos resto R.
R = resto[ ]
D.2r
G

Perfomance del Protocolo de Ventana deslizante
Sea un Host A, que usa protocolo de ventana deslizante, si debe transmitir un archivo de unos 10 GB con un Host B
Window size = 64KB
RTT de la red es de 1 segundo

Cual es la velocidad esperada con que el emisor envia datos?
64KB/s

Sliding Window
Host A
Host B
ACK
Window Size
Round-trip time
(1) RTT > Window size
(Gp:) ACK
(Gp:) Window Size
(Gp:) Round-trip time
(Gp:) (2) RTT = Window size

ACK
(Gp:) Window Size

(Gp:) ???

Utilización vs RTT normalizado
Fuente : Stallings W . Comunicaciones y Redes de Computadores- 7 Edición

Técnicas de identificación de tramas
Contador de caracteres: posibles problemas por pérdida de sincronismo.
Caracteres de inicio y final con caracteres de relleno: normalmente ASCII DLE STX para inicio y DLE ETX para final, con DLE de relleno.
Secuencia de bits indicadora de inicio y final, con bits de relleno: normalmente 01111110; si en los datos aparecen cinco bits seguidos a 1 se intercala automáticamente un 0.
Violaciones de código a nivel físico: se utiliza en algunas redes locales.

Protocolos de ventana deslizante
El protocolo puede ser:
Retroceso n: no se acepta una trama hasta haber recibido las anteriores
Repetición selectiva: se admite cualquier trama en el rango esperado y se pide solo la que falta.
Repetición selectiva es más complejo pero más eficiente, y requiere mas espacio en buffers en el receptor.
Tamaño de ventana:
Retroceso n: Número de secuencia – 1
Repetición selectiva: Número de secuencia/2

Corrección de Errores
FEC (Forward Error Correction)
Significa corrección de errores a posteriori y se utiliza en sistemas sin retorno o sistemas en tiempo real donde no se puede esperar a la retransmisión para mostrar los datos.
Básicamente consiste en codificar en el transmisor cada bloque de k bits de la trama en palabras de n bits, siendo n>k. El receptor decodifica las palabras en los bloques originales aunque éstos tuviesen algún error.

Corrección de Errores
FEC.
Los bits añadidos, conocidos como de redundancia, hacen posible detectar errores y deducir el dato que se transmitió.

Corrección de Errores
FEC
Se dispone de los siguientes tipos:
FEC a bloques.
Sus variantes más usadas:
BCH.
RS (Reed Solomon).
FEC convolucional.
Aplica el algoritmo Viterbi.

Corrección de Errores
FEC a bloques.
Se denomina Distancia Hamming entre dos códigos al número de símbolos en que se diferencian.
Peso de una palabra: número de unos que tiene.
Distancia de hamming: Número de bits en que difieren dos palabras.

Corrección de Errores
FEC a bloques. Distancia Hamming.

10001110 11100101
00111000 11110111
d=5 d=2
Peso de la suma de las 2 palabras.
10001110 11100101
+ 00111000 +11110111
=10110110 (peso 5) =00010010 (peso 2)

Corrección de Errores
FEC a bloque. Distancia Hamming.
Cuanto mayor sea la distancia de hamming entre dos palabras, más difícil será que un error en la transmisión convierta una en la otra, ya que será necesario alterar d bits.
Un código de distancia hamming d será capaz de detectar errores en d-1 bits.
Un código de distancia hamming d será capaz de corregir errores en (d-1)/2 bits.
Para corregir errores en d bits hará falta un código con distancia de hamming 2d+1.

Corrección de Errores
FEC a bloques. Distancia Hamming.
Códigos de control de paridad.
Se añade un bit de paridad al final de la palabra de forma que el número total de unos, incluído el bit de paridad sea par (paridad par) o impar (paridad impar).
Paridad par: 1011000 1
Paridad impar: 1101011 0
Este código tiene una distancia de hamming igual a 2, así que es capaz de detectar errores en 1 bit.

Corrección de Errores
FEC a bloques. Distancia Hamming.
Códigos de control de paridad.
Si la transmisión se realiza por bloques, se pueden añadir bits de paridad adicionales.

Distancia de hamming 4. Puede corregir errores en 1 bit y detectar errores en 1, 2 ó 3 bits.

Corrección de Errores
FEC a bloques. Distancia Hamming.
Códigos de hamming.
Son un subconjunto de los códigos de control de paridad, en los cuales se disponen los bits de paridad de forma que permitan localizar la presencia de errores en el mensaje.
Su distancia de hamming mínima es 3.
Para palabras de L bits, hace falta que R de esos bits sean de paridad para poder corregir un error en un bit, donde:
L £ 2R – 1
R será el menor número entero que cumpla esta condición

Corrección de Errores
FEC a bloques. Distancia Hamming.
Códigos de hamming.
Cada bit de paridad debe controlar un conjunto distinto de bits de información.
Un error en un bits de información debe afectar a 2 o más bits de paridad.
Para el cálculo de los bits de paridad sólo se pueden utilizar bits de información no se pueden incluir los otros bits de paridad.
Ejemplo:

Corrección de Errores
FEC a bloques. Distancia Hamming.
Códigos de hamming. Código óptimo.
Se numeran los bits de la palabra código empezando por 1.Los bits potencia de 2 serán de redundancia y el resto de datos.
Cada bits de datos contribuye a varios bits de redundancia, que se determinan descomponiendo la posición del bit en suma de potencias de 2.
Ejemplo: 11 = 1 + 2 + 8
Si se produce un error, el bit erróneo será el situado en la posición que se obtenga sumando las posiciones de los bits de redundancia incorrectos.

Corrección de Errores
FEC a bloques. Distancia Hamming.
Códigos de hamming. Código óptimo.
Ejemplo de código óptimo para caracteres de 7 bits.

Corrección de Errores
FEC a bloques. Código Hamming H.
Usado en algunos radioenlaces digitales en la década de los '80. En particular la versión H(555,544).

Permite corregir 2 errores en la secuencia de 544 bits de información.

Corrección de Errores
FEC a bloques. Código BCH.
Bose-Chaudhuri-Hocquenghen.
Es el código más conveniente para errores independientes. Los parámetros definidos son:
Longitud del bloque: N=2M-1 M>=3
Bits de información: I=N-M.t
Distancia mínima: d=2.t+1

Corrección de Errores
FEC a bloques. Código BCH.
Es usado por ejemplo en telefonía celular analógica AMPS en el canal de control bajo la versión BCH(48,36) y BCH(40,28).

En codificadores digitales de TV a 34Mb/s se utiliza el codec BCH(511,493) para corregir 2 errores por bloque.

Corrección de Errores
FEC a bloques. Código RS.
Reed-Solomon.
Es una variante del BCH y la más apropiada para ráfagas de errores. Los parámetros definidos:
Bits por símbolo: m
Longitud del bloque: N=m.2m-1
Bits de información: (N-I)=m.2t
Distancia mínima: d=m.(2.t+1)

Corrección de Errores
FEC a bloques. Código RS.
En general el número de errores corregidos son t ráfagas de m bits en una palabra de código.Por ejemplo:
En RS(60,40) se corrigen 2 ráfagas de 4 bits errados.
Una aplicación, entre otras, es en radioenlaces digitales de 140Mb/s en la versión RS(65/62) para corregir 4 errores en 4 bloques.